package algorthm.systemTraning.bucketSort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Random;

/**
 * @className: BucketSort
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/10/8 16:53
 */
public class BucketSort {
    private static Logger logger = LoggerFactory.getLogger(BucketSort.class);
    public static class Node implements Comparable<Node> {
        public int num ;
        public Node next ;
        public static void insert(Node pre , Node cur){
            Node tmp = pre.next;
            pre.next = cur ;
            cur.next = tmp ;
        }

        public int compareTo(Node o) {
            return this.num - o.num;
        }
        public Node(int num){
            this.num = num ;
        }

    }
    public static void sort(int[] array){
        Node[] nodes = new Node[array.length];
        for(int i : array){
            put(nodes , i);
        }
        int idx = 0 ;
        for(Node node : nodes){
            idx = compact(array , idx ,node);
        }
    }
    public static int compact(int[] array , int idx , Node node){
        Node curr = node ;
        while(curr != null){
            array[idx++] = curr.num ;
            curr = curr.next ;
        }
        return idx ;
    }
    public static void put(Node[] nodes , int i){
        int idx = i/100;
        if(null == nodes[idx]){
            nodes[idx] = new Node(i);
        }else{
            Node cur = new Node(i);
            Node pre = null;
            Node next = nodes[idx] ;
            while(next != null){
                if(next.num >= i){
                    if(null == pre){
                        pre = nodes[idx];
                        nodes[idx] = cur ;
                        cur.next = pre ;
                    }else{
                        Node.insert(pre , cur);
                    }
                    break ;
                }
                pre = next ;
                next = next.next ;
            }
            if(null == next){
                pre.next = cur ;
            }
        }
    }
    public static int[] randomArray(int range , int size){
        Random r = new Random();
        int newSize = r.nextInt(size) + 1;
        int[] array = new int[newSize];
        for(int i = 0 ;i < newSize ; i++){
            array[i] = r.nextInt(range);
        }
        return array ;
    }
    public static int[] copyOf(int[] array){
        int[] ans = new int[array.length];
        for(int i = 0 ; i < array.length ; i++){
            ans[i] = array[i];
        }
        return ans ;
    }
    public static void compare(int range , int size , int times){
       int[] array = null ;
       int[] array2 = null ;
       int[] arrayBak = null ;
       for(int i = 0 ; i < times ; i++){
            array = randomArray(range , size);
            array2 = copyOf(array);
            arrayBak = copyOf(array);
            sort(array);
            Arrays.sort(array2);
            if(!Arrays.equals(array ,array2)){
                System.out.println("Oops");
            }
       }
    }
    public static void main(String[] args){
        compare(99 , 40 , 300000);
    }

}
